

class Solution:
    def __init__(self):
        self.w = []
        self.v = []
        self.n = 0
        self.m = 0
        self.best = []
        self.max_val = -1
        self.selected = []

    def search(self, i):
        if i >= self.n:
            self.check()
        else:
            self.best[i] = 0
            self.search(i + 1)
            self.best[i] = 1
            self.search(i + 1)

    def check(self):
        weight = 0
        value = 0
        selected = []
        for i in range(self.n):
            if self.best[i]:
                weight += self.w[i]
                value += self.v[i]
                selected.append(i)

        if weight <= self.m and value >= self.max_val:
            self.max_val = value
            self.selected = selected

    def solve(self):
        self.w = [10, 20, 30, 40, 50]
        self.v = [20, 30, 65, 40, 60]
        self.n = len(self.w)
        self.m = 100
        self.best = [0] * self.m
        self.max_val = -1
        self.selected = []
        self.search(0)
        return self.max_val, self.selected


if __name__ == '__main__':
    s = Solution()
    val, selected = s.solve()
    print(val)
    print(selected)
